// https://leetcode.cn/problems/game-of-life/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用位运算原地更新细胞状态，最低位存储当前状态，次低位存储下一状态
// 2. 遍历每个细胞，统计八个方向的活细胞数量
// 3. 根据游戏规则使用位操作设置下一状态
// 4. 最后通过右移操作统一更新为下一代状态
// 5. 时间复杂度：O(M×N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
private:
    int m, n;
    const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
private:
    int getLiveNums(vector<vector<int>>& board, int a, int b)
    {
        int nums = 0;
        for (int i = 0 ; i < 8 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] & 1)
            {
                nums++;
            }
        }
        return nums;
    }
public:
    void printBoard(vector<vector<int>>& board)
    {
        for (const auto& v : board)
        {
            for (const int& num : v)
            {
                cout << num << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
public:
    void gameOfLife(vector<vector<int>>& board) 
    {
        m = board.size(), n = board[0].size();

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                int num = getLiveNums(board, i, j);
                if (board[i][j] == 1)
                {
                    if (num >= 2 && num <= 3)
                    {
                        board[i][j] |= 2;
                    }
                }
                else
                {
                    if (num == 3)
                    {
                        board[i][j] |= 2;
                    }
                }
            }
        }

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                board[i][j] >>= 1;
            }
        }

        return ;
    }
};

int main()
{
    vector<vector<int>> board1 = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
    vector<vector<int>> board2 = {{1,1},{1,0}};

    Solution sol;

    sol.gameOfLife(board1);
    sol.gameOfLife(board2);

    sol.printBoard(board1);
    sol.printBoard(board2);

    return 0;
}